import java.util.ArrayList;

import info.gridworld.grid.AbstractGrid;
import info.gridworld.grid.Location;

/**
 * A <code>SparseBoundedGrid</code> is a rectangular grid with a finite number of
 * rows and columns. <br />
 * The implementation of this class is testable on the AP CS AB exam.
 */
public class SparseBoundedGrid<E> extends AbstractGrid<E>
{
    private SparseGridNode[] occ;
    private int rows;
    private int cols;

    /**
     * Constructs an empty bounded grid with the given dimensions.
     * (Precondition: <code>rows > 0</code> and <code>cols > 0</code>.)
     * @param rows number of rows in BoundedGrid
     * @param cols number of columns in BoundedGrid
     */
    public SparseBoundedGrid(int rows, int cols)
    {
        if (rows <= 0)
            throw new IllegalArgumentException("rows <= 0");
        if (cols <= 0)
            throw new IllegalArgumentException("cols <= 0");
        this.rows = rows;
        this.cols = cols;
        occ = new SparseGridNode[rows];
    }

    public int getNumRows()
    {
        return rows;
    }

    public int getNumCols()
    {
        // Note: according to the constructor precondition, numRows() > 0, so
        // theGrid[0] is non-null.
        return cols;
    }

    public boolean isValid(Location loc)
    {
        return 0 <= loc.getRow() && loc.getRow() < getNumRows()
                && 0 <= loc.getCol() && loc.getCol() < getNumCols();
    }

    public ArrayList<Location> getOccupiedLocations()
    {
        ArrayList<Location> theLocations = new ArrayList<Location>();

        // Look at all grid locations.
        for (int r = 0; r < getNumRows(); r++)
        {
        	SparseGridNode n = occ[r];
        	while (n != null)
        	{
        		Location loc = new Location(r, n.getCol());
                if (get(loc) != null)
                    theLocations.add(loc);
                n = n.getNextNode();
        	}    
        }
        return theLocations;
    }

    @SuppressWarnings("unchecked")
	public E get(Location loc)
    {
        if (!isValid(loc))
            throw new IllegalArgumentException("Location " + loc
                    + " is not valid");
        SparseGridNode n = occ[loc.getRow()];
        while (n != null)
        {
        	if (loc.getCol() == n.getCol())
        	{
        		return (E) n.getObject();
        	}
        	n = n.getNextNode();
        }
        return null;
    }

    public E put(Location loc, E obj)
    {
        if (!isValid(loc))
            throw new IllegalArgumentException("Location " + loc
                    + " is not valid");
        if (obj == null)
            throw new NullPointerException("obj == null");

        // remove the old object to the grid.
        E oldOccupant = remove(loc);
        SparseGridNode n = occ[loc.getRow()];
        occ[loc.getRow()] = new SparseGridNode(obj, loc.getCol(), n);
        return oldOccupant;
    }

    public E remove(Location loc)
    {
        if (!isValid(loc))
            throw new IllegalArgumentException("Location " + loc
                    + " is not valid");
        
        // Remove the object from the grid.
        E r = get(loc);
        if (r == null)
        	return null;
        SparseGridNode n = occ[loc.getRow()];
        if (n != null)
        {
        	/*
        	 * find the first node
        	 */
        	if (n.getCol() == loc.getCol())
        	{
        		occ[loc.getRow()] = n.getNextNode();
        	}
        	else
        	{
        		SparseGridNode n1 = n.getNextNode();
        		while (n1 != null && n1.getCol() != loc.getCol())
        		{
        			n1 = n1.getNextNode();
        			n = n.getNextNode();
        		}
        		/*
        		 * remove the occupant if found
        		 */
        		if (n1 != null)
        		{
        			n.setNextNode(n1.getNextNode());
        		}
        	}
        }
        return r;
    }
}
